| layout | title | categories | tags | keywords | description | order |
|---|---|---|---|---|---|---|
post |
【HMM】理论篇 |
0x21_有监督学习 |
280 |
阅读本文前，请先保证已经了解马尔科夫过程
隐马尔可夫过程(HMM, Hidden Markov Model)用于描述由隐藏的马尔可夫链生成贯彻序列的过程1
隐藏的马尔科夫链随机生成序列，称为 状态序列(state sequence)
每个状态生成一个观测，观测组成的的序列，称为 observation sequence
Q是所有隐藏状态的集合，V是所有可能地观测的集合
N是所有可能地状态数，M是所有可能地观测数
一个隐马尔可夫模型表示为$\lambda =(A,B,\pi) $
从定义知道，隐马尔科夫模型有两个基本假设：
- 齐次马尔可夫性假设：任意时刻t的状态，只与t-1状态有关，与其他时刻的状态无关。
- 观测独立性假设：t时刻的观测，只与t时刻的马尔可夫链有关。
- 概率计算问题。给定模型$\lambda =(A,B,\pi)$和观测序列$$O={o_1,o_2,...,o_T}$$，求观测序列发生的概率$P(O\mid \lambda)$
- 学习问题。已知观测序列$$O={o_1,o_2,...,o_T}$$,估计模型$\lambda =(A,B,\pi)$中的参数，使得$P(O\mid \lambda)$最大(也就是MLE方法)
- 预测问题。已知模型$\lambda =(A,B,\pi)$，以及观测序列$$O={o_1,o_2,...,o_T}$$，求最可能的状态序列$$I={i_1,i_2,...,i_T}$$, 也就是使得$P(I\mid O)$最大的I
这是一个不太可行的方法。
先算出所有状态的概率，再求出所有观测的概率。
最后加总
算法复杂度$O(TN^T)$
定义前向概率$\alpha_t(i)=P(o_1,o_2,...o_t,i_t=q\mid \lambda)$
前向算法对t=1:T-1，每步迭代求当前序列发生的概率
（算法略）
算法复杂度为$O(N^2T)$
定义后向概率$\beta_t(i)=P(o_{t+1},o_{t+2},...o_T\mid i=q_i,\lambda)$
包括监督学习法和Baum-Welch算法（也就是EM算法）
已知$${(O_1,I_1),(O_2,I_2),...,(O_S,I_S)}$$
具体方法是记频数，然后用频数代替概率
(李航《统计学习方法》上写，这个方法是监督学习法，而且是极大似然估计法，我的理解是这样的：)
- 叫做监督学习法，是因为需要取得状态数据，这往往需要很大的代价。
- 叫做极大似然估计法，是因为记频数这种方法可以使似然值最大化。
给定$${O_1,O_2,...,O_S}$$,求$\lambda=(A,B,\pi)$的参数
用极大似然估计来求解。
在求最优似然值时，用EM算法
有两种解决此问题的算法
近似算法 ：简单，但有误差的
维特比算法：用的是动态规划的原理。